The eigenvalues of a matrix polynomial can be determined classically bysolving a generalized eigenproblem for a linearized matrix pencil, for instanceby writing the matrix polynomial in companion form. We introduce a generalscaling technique, based on tropical algebra, which applies in particular tothis companion form. This scaling, which is inspired by an earlier work ofAkian, Bapat, and Gaubert, relies on the computation of "tropical roots". Wegive explicit bounds, in a typical case, indicating that these roots provideaccurate estimates of the order of magnitude of the different eigenvalues, andwe show by experiments that this scaling improves the accuracy (measured bynormwise backward error) of the computations, particularly in situations inwhich the data have various orders of magnitude. In the case of quadraticpolynomial matrices, we recover in this way a scaling due to Fan, Lin, and VanDooren, which coincides with the tropical scaling when the two tropical rootsare equal. If not, the eigenvalues generally split in two groups, and thetropical method leads to making one specific scaling for each of the groups.
展开▼